分割等和子集

class Solution:
    def partition(self , nums: List[int]) -> bool:
        '''找重叠子问题'''
        '''不能只靠脑子想'''
        target = sum(nums)
        if target % 2 != 0:
            return False
        dp = [[0 for line in range(target//2 + 1)] for row in range(len(nums))]
        for i in range (1,target//2 + 1):
            if i < nums[0] :
                dp[0][i] = dp[0][i-1]
            else :
                dp[0][i] = nums[0]
        for i in range(1,len(nums)):
            for j in range(1, target//2 + 1):
                if j < nums[i] :
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], nums[i] + dp[i-1][j-nums[i]])
        if dp[len(nums)-1][target//2] == target//2:
            return True
        else :
            return False


但是会超时 ，没有做优化。